1. Field of the Invention
The invention relates generally to methods and apparatus for converting a lightweight monitor to a heavyweight monitor in an object-based computing system. More particularly, the invention relates to methods and apparatus for atomically converting a lightweight monitor associated with a contended object to a corresponding heavyweight monitor in an object-based computing system.
2. Related Art
Within an object-based environment, threads are often used to satisfy requests for services. A thread may be thought of as a xe2x80x9csketch padxe2x80x9d of storage resources, and is essentially a single sequential flow of control within a computer program. In general, a thread, or a xe2x80x9cthread of control,xe2x80x9d is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside. As will be appreciated by those skilled in the art, when a method is activated with respect to a thread, an activation is xe2x80x9cpushedxe2x80x9d on the execution stack of the thread. When the method returns, or is deactivated, the activation is xe2x80x9cpoppedxe2x80x9d from the execution stack. Since an activation of one method may activate another method, an execution stack operates in a first-in-last-out manner.
During the execution of an object-based program, a thread may attempt to execute operations that involve multiple objects. On the other hand, multiple threads may attempt to execute operations that involve a single object. Frequently, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. That is, only one thread may be allowed to execute a synchronized operation on a particular object at one time. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method to first synchronize with the object that the method is invoked on, and desynchronize with that object when the method returns. Synchronizing a thread with an object generally entails controlling access to the object using a synchronization construct before invoking the method.
Synchronization constructs such as locks, mutexes, semaphores, and monitors may be used to control access to shared resources during periods in which allowing a thread to operate on shared resources would be inappropriate. By way of example, in order to prevent more than one thread from operating on an object at any particular time, objects are often provided with locks. The locks are arranged such that only the thread that has possession of the lock for an object is permitted to execute a method on that object.
Typically, a thread is permitted to execute a synchronized operation on an object if it successfully acquires the lock on the object. While one thread holds the lock on an object, other threads may be allowed to attempt to execute additional synchronization operations on the object, and may execute non-synchronized operations on the object. Thread synchronization is a process by which threads may interact to check the status of objects, whether the objects are locked or unlocked, while allowing only the thread which holds an object lock to execute synchronized operations on the locked object. Thread synchronization also enables threads to obtain and remove object locks.
When threads are synchronized, in order to make certain that only the thread that possesses an object lock is allowed to operate on a locked object, synchronization constructs are generally provided. One such synchronization construct is known in the art as the monitor. Typically, monitors are implemented using low-level synchronization primitives such as mutexes and the like. Even though programs may perform monitor operations on any object, it is generally too space inefficient to include a monitor implementation for every object. One such synchronization construct is referred to as a monitor. Generally, a monitor is arranged such that only the thread that owns the monitor associated with an object is permitted to execute a synchronized operation on that object. Monitors may be either lightweight or heavyweight. Typically, lightweight monitors are preferable for objects that are not subject to contention, whereas heavyweight monitors are preferably used to handle contended monitor operations.
One particular implementation of a lightweight monitor is described in xe2x80x9cThin Locks: Featherweight Synchronization for Javaxe2x80x9d by David F. Bacon et al. (1998), 258-268 which is incorporated by reference in its entirety. As described, the lightweight monitor is formed of bits reserved in the object header that identifies which thread, in the form of a thread ID, owns the lightweight monitor and therefore has locked the associated object. Typically, lightweight monitors are used for objects that are not subject to contention, i.e.; do not have wait, notify, or notifyALL operations performed upon them. FIG. 1A illustrates an object header 100 and an associated lightweight monitor 102. The lightweight monitor 102 includes a thread identifier field (also referred to as an owner field) 104 containing the thread ID of the thread that owns the lightweight monitor 102. The lightweight monitor 102 also includes a recursion counter 106 indicating the number of times that the current thread has re-entered the lightweight monitor. The lightweight monitor 102 also includes a heavyweight monitor flag 108 used to identify the lightweight monitor 102 as a lightweight monitor when the heavyweight monitor flag is set to xe2x80x9c0xe2x80x9d.
In the situation where the owner field 104 is zero, the lightweight monitor 102 is unowned and therefor unlocked. If, however, the owner field 104 contains a thread ID representative of the current thread that owns the lightweight monitor 102.
In order to enter a lightweight monitor, a thread 110 typically performs a compare and swap operation on the object header 100 that contains the lightweight monitor 102. In a compare and swap operation, the new value of the compare and swap operator is the thread ID associated with the thread 110 and the comperand of the compare and swap operator is zero. With this arrangement, if the compare and swap operation is successful, then the thread ID, recursion counter, and all flags (such as the heavyweight monitor flag 108) in the lightweight monitor 102 had been all been initially zero indicating that the lightweight monitor 102 was un-owned and, therefor, un-locked. After the successful completion of the compare and swap operation, the owner field 104 now contains the thread ID associated with the thread 110 indicating that the thread 110 owns the lightweight monitor 102 and has therefor locked the lightweight monitor 102.
In those cases where a thread is re-entering a monitor that it already owns (i.e.; the thread is re-entrant), the re-entering thread must first increment the recursion counter 106 without causing an overflow condition. In those situations where a re-entering thread does cause an overflow condition, the re-entering thread must convert the lightweight monitor 102 into a heavyweight monitor 114 that is built upon a system monitor 116. It should be noted that, by design, only the current owner of the system monitor 116 is capable of converting the lightweight monitor 102 to the heavyweight monitor 114. Typically, this conversion is accomplished by performing a compare and swap operation on the object header 100 with the new value of the compare and swap operator being a heavyweight monitor pointer corresponding to the newly created heavyweight monitor 114. In this way, after the successful compare and swap operation, the object header 100 contains the heavyweight monitor pointer.
The heavyweight monitor 114 includes a recursion counter field 118 that is updated every time a particular thread re-enters the system monitor 116. The heavyweight monitor 114 also includes a heavyweight monitor owner field 120. The system monitor 116 includes a system monitor owner field 122 indicative of the current owner of the system monitor 116. The system monitor 116 is also arranged to perform particular thread operations, such as enter, exit, wait, and notify. Since the current owner (i.e.; thread 110) of the lightweight monitor 102 is the only thread capable of converting the lightweight monitor 102 to the heavyweight monitor 114, the owner of the heavyweight monitor 114 and the embedded system monitor 116 must be the same, i.e., thread 110.
Referring now to FIG. 1B, assume that a second thread 124 attempts to enter the lightweight monitor 102 that is currently owned by the thread 110. As before, the thread 124 will attempt to enter the lightweight monitor 102 by performing a compare and swap operation. In this case, however, the compare and swap operation will fail since the owner field 104 contains the thread ID corresponding to the thread 110 indicating that it owns the lightweight monitor 102. At this point, there is contention for ownership of the lightweight monitor 102 between the thread 124 and the thread 110. Since only the thread 110 (as owner of the system monitor 116) can convert the lightweight monitor 102 to the heavyweight monitor 114, the thread 124 enters a spin-lock loop until the lightweight monitor 102 is released by the thread 110. By spin lock loop, it is meant that the thread 124 enters a wait queue until such time as the thread 110 unlocks the lightweight monitor 102. As well known in the art, spin locking in general is undesirable due in part to its inefficient use of system resources. Spin locking is especially inefficient in those cases where the lightweight monitor 102 is locked for a long period of time causing other threads waiting for the lightweight monitor 102 to spin lock. In addition, xe2x80x9cstarvingxe2x80x9d lower priority threads is a distinct possibility in those situations where higher priority threads and lower priority threads are both spin locked on the lightweight monitor 102.
Therefore, what is desired is an efficient method and apparatus for resolving monitor contention in an object-based system.
Broadly speaking, the invention relates to an improved method, apparatus and computer system for efficiently converting a lightweight monitor associated with a contended object into a heavyweight monitor. According to one aspect of the invention, for a first thread to execute a synchronous operation on an object owned by a second thread, the first thread creates a new heavyweight monitor and sets the second thread as owner of the newly created heavyweight monitor. The first thread then enters the heavyweight monitor. In this manner, the first thread is not required to spin lock until such time as the second thread unlocks the object.
The invention can be implemented in numerous ways, including as a method, a computer system, and an apparatus. Several embodiments of the invention are discussed below. Methods and apparatus are disclosed. According to one aspect of the present invention, a computer-implemented method for converting a lightweight monitor to a heavyweight monitor when an object owned by a second thread is unavailable to a first thread includes determining ownership of the object associated with the lightweight monitor. If it is determined that the second thread owns the object, the first thread creates a new heavyweight monitor. The first thread then sets second thread as the owner of the newly created heavyweight monitor. The first thread then enters the newly created heavyweight monitor.
According to yet another aspect of the present invention, a computer system includes a memory and a plurality of threads. The computer system also includes a processor coupled to the memory and an object that includes an object header, the object header being arranged to contain a lightweight monitor that includes information relating to the ownership of object. A first thread selected from the plurality of threads that has locked the object as indicated by a first thread ID included in the lightweight monitor; and a second thread selected from the plurality of threads, the second thread being arranged to convert the lightweight monitor to a corresponding heavyweight monitor owned by the first thread when the object is not available to the second thread.
According to still another aspect of the invention, a computer program product for converting a lightweight monitor into a heavy weight monitor when a first thread attempts to execute a synchronous operation on an object having an object header containing the lightweight monitor is disclosed. The computer program product includes computer code that determines ownership of the object, that creates a heavyweight monitor when it is determined that the object is owned by a second thread, that sets ownership of the heavyweight monitor to the second thread; and computer code that causes the first thread to enter the heavyweight monitor; and a computer readable medium that stores the computer codes.